#include "DynamicArray.h"
#include <iostream>
#include <cmath>

// 带参构造
DynamicArray::DynamicArray(size_t capacity):size(0), capacity(capacity)
{
    array = new ElementType[capacity];
}

// 拷贝构造
DynamicArray::DynamicArray(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}

// 运算符重载
DynamicArray &DynamicArray::operator=(const DynamicArray &a)
{
    delete []array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for(int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    return *this;
}

// 析构函数
DynamicArray::~DynamicArray()
{
    delete []array;
}

// 数组大小
size_t DynamicArray::Size()
{
    return size;
}

// 扩容接口
void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = (size > capacity) ? capacity : size;

    ElementType *newP = new ElementType[capacity];
    for(size_t i = 0; i <size; i++)
    {
        newP[i] = array[i];
    }
    delete []array;
    array = newP;
}

// 尾部插入 O(1)
void DynamicArray::InsertTail(const ElementType &element) 
{
    if(size >= capacity);
        ReSize(2 * capacity);
    array[size++] = element; 
}

// 头部插入 O(n)
void DynamicArray::InsertHead(const ElementType &element) 
{
    if(size >= capacity);
        ReSize(2 * capacity);
    for(size_t i = size; i > 0; i--) 
    {
        array[i] = array[i-1];
    }
    array[0] = element;
    size++;
}

// 中间插入 O(n)
void DynamicArray::InsertByIndex(int index, const ElementType &element) 
{
    //  非法位置排除
    if(index < 0 || index > size)
        return;
    if(size >= capacity);
        ReSize(2 * capacity);
    for(size_t i = size; i > index; i--) 
    {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;  
}

// 按位置删除 O(n)
void DynamicArray::RemoveByIndex(int index) 
{
    //  非法位置排除
    if(index < 0 || index > size)
        return;
    for(size_t i = index; i < size - 1; i++) 
    {
        array[i] = array[i+1];
    }
    size--;
}

// 按值删除 O(n^2)
void DynamicArray::RemoveByElement(const ElementType &element) 
{
    for(int i = 0; i < size; i++) 
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 按位置查找 O(1)
// 返回值如果是int值，那不好区分这个值是元素还是下标，也就无法判断这个值的合法性
// 传值不行就传地址（口诀）
ElementType *DynamicArray::FindByIndex(int index) 
{
    // 没找到就返回空地址
    if(index < 0 || index >= size)
        return nullptr;
    // 如果找到了，就返回index位置的地址
    return &array[index];
}

// 按值查找 O(n)
// 返回下标，可能不止一个，所以返回值为数组
DynamicArray DynamicArray::FindByElement(const ElementType &element) 
{
    DynamicArray result;
    for(int i = 0; i < size; i++)
    {
        if(array[i] == element)
        {
            result.InsertTail(i);
        } 
    }
    return result;
}

// 按位置修改 O(1)
void DynamicArray::UpdateByIndex(int index, const ElementType &element) 
{
    if(index < 0 || index >= size)
        return;
    array[index] = element; 
}

// 按值修改
void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    for(int i = 0; i < size; i++)
    {
        if(array[i] == oldValue)
        {
            array[i] = newValue;
        } 
    }
}

// 排序
void DynamicArray::Sort()
{
    FastSort(0, size-1, 0, 2 * log2(size));
}

// 去重算法
void DynamicArray::Duplicate()
{
    for(int i = 1; i < size; i++)
    {
        if(array[i] == array[i-1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 归并算法（要背！！！）
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组
    DynamicArray result;
    // 遍历两个数组都没有到结尾
    while(first < this->size && second < a.size)
    {
        if(this->array[first] <= a.array[second])
            result.InsertTail(array[first++]);
        else
            result.InsertTail(a.array[second++]);
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

// 找交集
DynamicArray DynamicArray::FdInterSctn(const DynamicArray &a)
{
#if 0
    // O(n^2)
    DynamicArray result;
    for(int i = 0; i < size; i++) 
    {
        for(int j = 0; j < a.size; j++)
        {
            if(array[i] == a.array[j])
            {
                result.InsertTail(array[i]);
            }
        }
    }
    result.Sort();
    result.Duplicate();
    return result;
#endif

#if 1
    // O(n)
    DynamicArray result;
    size_t first = 0;
    size_t second = 0;
    while(first < size && second < a.size) 
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(array[first] > a.array[second])
        {
            second++;
        }
        else
        {
            first++;
        }
    }
    return result;
#endif   
}

// 找并集 O(n)
DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)
{
    size_t first = 0;
    size_t second = 0;
    DynamicArray result;
    while(first < size && second < a.size) 
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(array[first] > a.array[second])
        {
            result.InsertTail(array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

// 找补集 O(n)
DynamicArray DynamicArray::FindDifference(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;
    size_t second = 0;
    while(first < size && second < a.size) 
    {
        if(array[first] == a.array[second])
        {
            first++;
            second++;
        }
        else if(array[first] > a.array[second])
        {
            result.InsertTail(array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

// 判断两个数列是否相等 O(n)
bool DynamicArray::operator==(const DynamicArray &a)
{
    // return this->FindDifference(a).size == 0;
    if(size != a.size)
        return false;
    int first = 0;
    int second = 0;
    while(first < size && second < a.size)
    {
        if(array[first++] != a.array[second++])
            return false;
    }
    return true;
}

// 二分查找
size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while(left <= right)
    {
        size_t mid = (left & right) + ((left ^ right) >> 1);
        if(array[mid] == element)
            return mid;
        else if(array[mid] > element)
        {
            // 无符号数，0-1是一个超级大数
            if(mid == 0)
                return ULONG_MAX;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return ULONG_MAX;
}

// 是否是子序列
bool DynamicArray::IsChild(const DynamicArray &a)
{
#if 0
    // 无序 O(n)
    for(int i = 0; i < a.size; i++) 
    {
        // 没找到
        if(FindByElement(a.array[i]).size == 0)
        {
            return false;
        }
    }
    return true;
#endif

#if 1
    // 有序 O(n)
    int j = 0;
    for(int i = 0; i < size; i++) 
    {
        if(array[i] == a.array[j])
        {
            j++;
        }
    }
    return j == a.size;
#endif
}

// 是否是连续子序列（滑动窗口算法）
bool DynamicArray::IsCntnsChild(const DynamicArray &a)
{
    for(int i = 0; i <= size - a.size; i++) // O(n^2)
    {
        if(subsequence(i, a.size) == a)
        {
            return true;
        }
    }
    return false;
}

// 获取子序列
DynamicArray DynamicArray::subsequence(int index, size_t size)
{
    if(index < 0 || index + size > this->size)
        return DynamicArray();
    DynamicArray result;
    for(int i = index; i < index + size; i++)
    {
        result.InsertTail(array[i]);
    }
    return result;
}

// 插排（当快排递归深度过深的时候，不能再用快排，改用插排）
void DynamicArray::InsertSort(size_t start, size_t end)
{
    for(size_t i = start; i <= end; i++)
    {
        size_t j = i;
        ElementType temp = array[i];
        for(; j > start; j--)
        {
            if(array[j-1] > temp)
            {
                array[j] = array[j-1];
            }
            else
                break;
        }
        array[j] = temp;    
    }
}

// 分组函数
size_t DynamicArray::Partition(size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[left];
    while(left < right)
    {
        while(left < right && array[right] > temp)
            right--;
        if(left < right)
            array[left++] = array[right];
        while(left < right && array[left] < temp)
            left++;
        if(left < right)
            array[right--] = array[left];
    }
    array[left] = temp;
    return left;
}

// 快排
void DynamicArray::FastSort(size_t start, size_t end, size_t depth, size_t MaxDepth)
{
    if(start >= end)
        return;
    // 递归过深会导致栈溢出
    // 如果超过了最大深度
    if(depth > MaxDepth)
    {
        // 使用插入排序
        InsertSort(start, end);
    }
    // 如果没有超过最大深度，继续快排分组
    else
    {
        size_t par = Partition(start, end);
        if(par != 0)
            FastSort(start, par-1, depth+1, MaxDepth);
        FastSort(par+1, end, depth+1, MaxDepth);
    }
}

void DynamicArray::show()
{
    for(int i = 0; i < size; i++)
    {
        std::cout<<array[i]<<" ";
    }
    std::cout<<std::endl;
}